// https://www.lintcode.com/problem/valid-parentheses/

public class Solution {
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    public boolean isValidParentheses(String s) {
        // write your code here
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (('(' == ch) || ('[' == ch) || ('{' == ch)) {
                stack.push(ch);
            }
            else if (')' == ch) {
                if ((!stack.isEmpty()) && (stack.peek() == '(')) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
            else if (']' == ch) {
                if ((!stack.isEmpty()) && (stack.peek() == '[')) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
            else { // }
                if ((!stack.isEmpty()) && (stack.peek() == '{')) {
                    stack.pop();
                }
                else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}